package com.aaron.leetcode.lc37;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution37_1 {

    //回溯算法 sodoku 数独
    //board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]];
    //横竖、九宫内不能重复的情况不一定是最后答案=>一定是最后答案。。。，之前不对因为自己循环写了个0-9可填。。。
    //确保横竖、九宫内123456789出现一次
    static char[][] board = new char[9][9];
    static char[][] board2 = new char[9][9];

    static {
        board[0] = new char[]{'5', '3', '.', '.', '7', '.', '.', '.', '.'};
        board[1] = new char[]{'6', '.', '.', '1', '9', '5', '.', '.', '.'};
        board[2] = new char[]{'.', '9', '8', '.', '.', '.', '.', '6', '.'};
        board[3] = new char[]{'8', '.', '.', '.', '6', '.', '.', '.', '3'};
        board[4] = new char[]{'4', '.', '.', '8', '.', '3', '.', '.', '1'};
        board[5] = new char[]{'7', '.', '.', '.', '2', '.', '.', '.', '6'};
        board[6] = new char[]{'.', '6', '.', '.', '.', '.', '2', '8', '.'};
        board[7] = new char[]{'.', '.', '.', '4', '1', '9', '.', '.', '5'};
        board[8] = new char[]{'.', '.', '.', '.', '8', '.', '.', '7', '9'};
    }
    /*
        [[".",".","9","7","4","8",".",".","."],["7",".",".",".",".",".",".",".","."],[".","2",".","1",".","9",".",".","."],[".",".","7",".",".",".","2","4","."],[".","6","4",".","1",".","5","9","."],[".","9","8",".",".",".","3",".","."],[".",".",".","8",".","3",".","2","."],[".",".",".",".",".",".",".",".","6"],[".",".",".","2","7","5","9",".","."]]
     */
    static {
        board2[0] = new char[]{'.','.','9','7','4','8','.','.','.'};
        board2[1] = new char[]{'7','.','.','.','.','.','.','.','.'};
        board2[2] = new char[]{'.','2','.','1','.','9','.','.','.'};
        board2[3] = new char[]{'.','.','7','.','.','.','2','4','.'};
        board2[4] = new char[]{'.','6','4','.','1','.','5','9','.'};
        board2[5] = new char[]{'.','9','8','.','.','.','3','.','.'};
        board2[6] = new char[]{'.','.','.','8','.','3','.','2','.'};
        board2[7] = new char[]{'.','.','.','.','.','.','.','.','6'};
        board2[8] = new char[]{'.','.','.','2','7','5','9','.','.'};
    }

    //true已经找到正确答案
    boolean flag = false;

    //计算该位置可填范围
    List<Character> calcSpace(int m, int n,char[][] board){
        Set<Character> space = new HashSet<>();
        //该行出现过的数字
        for (char s : board[m]) {
            space.add(s);
        }

        //该列出现过的数字
        for (int i = 0; i < 9; i++) {
            space.add(board[i][n]);
        }

        //九宫格内出现过的数字
        int m1 = (m / 3) * 3;
        int n1 = (n / 3) * 3;

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                space.add(board[m1 + i][n1 + j]);
            }
        }

        //移除.
        space.remove('.');
        List<Character> ans = new ArrayList();
        //49=>1
        for (char i = 49; i < 58; i++) {
            //没出现过的
            if (!space.contains(i)) {
                ans.add(i);
            }
        }
        return ans;
    }


    public boolean solve(char[][] board) {
        if (flag) {
            return false;
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (flag) {
                    return false;
                }
                if ('.' == board[i][j]) {
                    List<Character> space = calcSpace(i, j,board);
                    if (null == space || space.isEmpty()) {
                        //如果space为空，则需要全部重来，要记录每一个
                        return false;
                    }
                    boolean nextRes = true;
                    for (Character character : space) {
                        board[i][j] = character;
                        nextRes = solve(board);
                        //防止找到答案后把路径还原了
                        if (flag) {
                            return false;
                        }
                        board[i][j] = '.';
                    }
                    if (!nextRes) {
                        return false;
                    }
                }
            }
        }
        flag = true;
        return false;
    }

    public void solveSudoku(char[][] board) {
        solve(board);
    }
    public static void main(String[] args) {
        Solution37_1 solution37_1 = new Solution37_1();
//        solution37_1.calcSelectSpace(8, 0, "2");
        board = board2;
        solution37_1.solveSudoku(board);
        for (int i = 0; i < board.length; i++) {
            for (char c : board[i]) {
                System.out.print(c + " ");
            }
            System.out.println();
        }
    }
}